/*
 * Triangulates a polygon using simple O(N^2) ear-clipping algorithm
 * Returns a Triangle array unless the polygon can't be triangulated,
 * in which case null is returned.  This should only happen if the
 * polygon self-intersects, though it will not _always_ return null
 * for a bad polygon - it is the caller's responsibility to check for
 * self-intersection, and if it doesn't, it should at least check
 * that the return value is non-null before using.  You're warned!
 */
using System;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using System.Collections.Generic;

namespace PolyDecomp
{
    public static class Triangulation
    {
        public static Triangle[] triangulatePolygon(List<Vector2> polygon)
        {

            if (polygon.Count < 3) return null;
            var vNum = polygon.Count;
            Triangle[] buffer = new Triangle[vNum];
            int bufferSize = 0;
            float[] xrem = new float[vNum];
            float[] yrem = new float[vNum];
            for (int i = 0; i < vNum; ++i)
            {
                xrem[i] = polygon[i].X;
                yrem[i] = polygon[i].Y;
            }
            Triangle toAdd;
            while (vNum > 3)
            {
                //Find an ear
                int earIndex = -1;
                for (int i = 0; i < vNum; ++i)
                {
                    if (isEar(i, xrem, yrem))
                    {
                        earIndex = i;
                        break;
                    }
                }

                //If we still haven't found an ear, we're screwed.
                //The user did Something Bad, so return null.
                //This will probably crash their program, since
                //they won't bother to check the return value.
                //At this we shall laugh, heartily and with great gusto.
                if (earIndex == -1) return null;


                //Clip off the ear:
                //  - remove the ear tip from the list

                //Opt note: actually creates a new list, maybe
                //this should be done in-place instead.  A linked
                //list would be even better to avoid array-fu.
                --vNum;
                float[] newx = new float[vNum];
                float[] newy = new float[vNum];
                int currDest = 0;
                for (int i = 0; i < vNum; ++i)
                {
                    if (currDest == earIndex) ++currDest;
                    newx[i] = xrem[currDest];
                    newy[i] = yrem[currDest];
                    ++currDest;
                }

                //  - add the clipped triangle to the triangle list
                int under = (earIndex == 0) ? (xrem.Length - 1) : (earIndex - 1);
                int over = (earIndex == xrem.Length - 1) ? 0 : (earIndex + 1);

                toAdd = new Triangle(new Vector2(xrem[earIndex], yrem[earIndex]), new Vector2(xrem[over], yrem[over]), new Vector2(xrem[under], yrem[under]));
                buffer[bufferSize] = toAdd;
                ++bufferSize;

                //  - replace the old list with the new one
                xrem = newx;
                yrem = newy;
            }
            toAdd = new Triangle(new Vector2(xrem[1], yrem[1]), new Vector2(xrem[2], yrem[2]), new Vector2(xrem[0], yrem[0]));
            buffer[bufferSize] = toAdd;
            ++bufferSize;

            Triangle[] res = new Triangle[bufferSize];
            for (int i = 0; i < bufferSize; i++)
            {
                res[i] = buffer[i];
            }
            return res;
        }

        public static Polygon[] polygonizeTriangles(Triangle[] triangulated)
        {
            Polygon[] polys;
            int polyIndex = 0;

            if (triangulated == null)
            {
                return null;
            }
            else
            {
                polys = new Polygon[triangulated.Length];
                bool[] covered = new bool[triangulated.Length];
                for (int i = 0; i < triangulated.Length; i++)
                {
                    covered[i] = false;
                }

                bool notDone = true;

                while (notDone)
                {
                    int currTri = -1;
                    for (int i = 0; i < triangulated.Length; i++)
                    {
                        if (covered[i]) continue;
                        currTri = i;
                        break;
                    }
                    if (currTri == -1)
                    {
                        notDone = false;
                    }
                    else
                    {
                        Polygon poly = new Polygon(triangulated[currTri]);
                        covered[currTri] = true;
                        int coveredcnt = covered.Count(x => x == true);
                        int prev_coveredcnt = coveredcnt - 1;
                        while (coveredcnt!=prev_coveredcnt)
                        {
                            prev_coveredcnt = coveredcnt;
                            for (int i = 0; i < triangulated.Length; i++)
                            {
                                if (covered[i]) continue;
                                Polygon newP = poly.add(triangulated[i]);
                                if (newP == null) continue;
                                //if (newP.isConvex())
                                //{
                                //    poly = newP;
                                //    covered[i] = true;
                                //}

                                if (newP.isGood())
                                {
                                    poly = newP;
                                    covered[i] = true;
                                }
                            }
                            coveredcnt = covered.Count(x => x == true);
                        }

                        polys[polyIndex] = poly;
                        polyIndex++;
                    }
                }
            }
            Polygon[] ret = new Polygon[polyIndex];
            for (int i = 0; i < polyIndex; i++)
            {
                ret[i] = polys[i];
            }
            return ret;
        }

        //Checks if vertex i is the tip of an ear
        public static bool isEar(int i, float[] xv, float[] yv)
        {
            float dx0, dy0, dx1, dy1;
            dx0 = dy0 = dx1 = dy1 = 0;
            if (i >= xv.Length || i < 0 || xv.Length < 3)
            {
                return false;
            }
            int upper = i + 1;
            int lower = i - 1;
            if (i == 0)
            {
                dx0 = xv[0] - xv[xv.Length - 1]; dy0 = yv[0] - yv[yv.Length - 1];
                dx1 = xv[1] - xv[0]; dy1 = yv[1] - yv[0];
                lower = xv.Length - 1;
            }
            else if (i == xv.Length - 1)
            {
                dx0 = xv[i] - xv[i - 1]; dy0 = yv[i] - yv[i - 1];
                dx1 = xv[0] - xv[i]; dy1 = yv[0] - yv[i];
                upper = 0;
            }
            else
            {
                dx0 = xv[i] - xv[i - 1]; dy0 = yv[i] - yv[i - 1];
                dx1 = xv[i + 1] - xv[i]; dy1 = yv[i + 1] - yv[i];
            }
            float cross = dx0 * dy1 - dx1 * dy0;
            if (cross > 0) return false;
            Triangle myTri = new Triangle(new Vector2(xv[i], yv[i]), new Vector2(xv[upper], yv[upper]), new Vector2(xv[lower], yv[lower]));
            for (int j = 0; j < xv.Length; ++j)
            {
                if (j == i || j == lower || j == upper) continue;
                if (myTri.isInside(xv[j], yv[j])) return false;
            }
            return true;
        }
    }
}